package test.n00100;


import java.util.Stack;

public class Problem00200 {
    public static void main(String[] args) {
        println("()");
    }

    public static void println(String s) {
        Solution ss = new Solution();
        System.out.println(s + "," + ss.isValid(s));
    }

    public static class Solution {

        /**
         * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
         * <p>
         * 有效字符串需满足：
         * <p>
         * 左括号必须用相同类型的右括号闭合。
         * 左括号必须以正确的顺序闭合。
         * <p>
         * 来源：力扣（LeetCode）
         * 链接：https://leetcode.cn/problems/valid-parentheses
         * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
         * <p>
         * 解题思路:
         * 栈结构
         *
         * @param s
         * @return
         */
        public boolean isValid(String s) {
            int len = s.length();
            if (len % 2 == 1) {
                return false;
            }

            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < len; i++) {
                char c = s.charAt(i);
                if (stack.isEmpty()) {
                    stack.push(c);
                    continue;
                }

                if (checkPair(stack.peek(), c)) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
            return stack.isEmpty();
        }

        public boolean checkPair(char left, char right) {
            if (left == '(' && right == ')') {
                return true;
            }
            if (left == '{' && right == '}') {
                return true;
            }
            if (left == '[' && right == ']') {
                return true;
            }
            return false;
        }
    }
}
